package com.hyb.algorithm.data.struct.tree;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

/**
 *
 *   230. 二叉搜索树中第K小的元素
 *   https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
 *
 *
 * @author: ybhu
 * @create: 2023/12/25 00:27
 */
public class KthSmallest {


    public static void main(String[] args) {

        TreeNode treeNode=new TreeNode(1);

        treeNode.left=new TreeNode(2);

        treeNode.left.left=new TreeNode(4);
        treeNode.left.right=new TreeNode(5);
        treeNode.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(6);


        List<Integer> list=  new InorderTraversal().inorderTraversal(treeNode);

        System.out.println(JSONObject.toJSON(list));

    }

    public int kthSmallest(TreeNode root, int k) {

        Deque<TreeNode> deque=new ArrayDeque<TreeNode>();

        while(root!=null|| !deque.isEmpty()){

            //中序遍历 先遍历左子树
            while(root!=null){
                deque.push(root);
                root=root.left;
            }

            //后进先出
            root=deque.pop();

            if(root==null){
                return -1;
            }

            --k;

            if(k==0){
                return root.val;
            }

            root=root.right;

        }

        return -1;
    }
}
